package 题目集.倍增算法.lca;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 货车运输 一共有n座城市，编号1 ~ n 一共有m条双向道路，每条道路(u, v, w)表示有一条限重为w，从u到v的双向道路
 * 从一点到另一点的路途中，汽车载重不能超过每一条道路的限重 每条查询(a, b)表示从a到b的路线中，汽车允许的最大载重是多少
 * 如果从a到b无法到达，那么认为答案是-1 一共有q条查询，返回答案数组 1 <= n <= 10^4 1 <= m <= 5 * 10^4 1 <= q
 * <= 3 * 10^4 0 <= w <= 10^5 1 <= u, v, a, b <= n 测试链接 :
 * https://www.luogu.com.cn/problem/P1967 容易想到，需要生成一个最大边生成树。
 * 第一思路：先生成最小生成树，然后dfs查找a~b点，记录下载重的最小值。会爆栈
 */
public class ch05_货车运输1_朴素dfs {

	static int[][] edges; // 存储所有的边，0：from,1:to。2:w
	static List<int[]>[] graph;
	static int n, m;
	static int maxn = (int) 1e4 + 10, maxm = (int) (5e4 + 10);
	static int[] p = new int[maxn], size = new int[maxn];

	public static void main(String[] args) {
		Reader sc = new Reader();
		n = sc.nextInt();
		m = sc.nextInt();
		graph = new List[n + 1];
		edges = new int[m][];
		for (int i = 1; i <= n; i++) {
			graph[i] = new ArrayList<>();
			p[i] = i;
			size[i] = 1;
		}
		for (int i = 0; i < m; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int w = sc.nextInt();
			edges[i] = new int[] { u, v, w };
		}
		List<int[]> result = kruskal();
		for (int[] edge : result) {
			graph[edge[0]].add(new int[] { edge[0], edge[1], edge[2] });
			graph[edge[1]].add(new int[] { edge[1], edge[0], edge[2] });
		}
		int q=sc.nextInt();
		for (int i = 0; i < q; i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int res = dfs(u, v, -1, Integer.MAX_VALUE);
			System.out.println(res);
		}
	}

	/**
	 * 朴素解法 会爆栈
	 *
	 * @param c：当前点
	 * @param e：目标点
	 * @param from：上一个点
	 * @param max：之前道路的最大值
	 */
	private static int dfs(int c, int e, int from, int max) {
		if (c == e) {
			return max;
		}
		for (int[] edge : graph[c]) {
			if (edge[1] != from) {
				int ans = dfs(edge[1], e, c, Math.min(max, edge[2]));
				if (ans != -1) {
					return ans;
				}
			}
		}
		return -1;
	}

	/**
	 * 返回最小生成树的所有关键边
	 */
	public static List<int[]> kruskal() {
		Arrays.sort(edges, (a, b) -> b[2] - a[2]);
		List<int[]> result = new ArrayList<>();
		for (int[] edge : edges) {
			if (find(edge[0]) != find(edge[1])) {
				union(edge[0], edge[1]);
				result.add(edge);
			}
		}
		return result;
	}

	private static void union(int a, int b) {
		if (size[p[a]] > size[p[b]]) {
			size[p[a]] += size[p[b]];
			p[b] = p[a];
		} else {
			size[p[b]] += size[p[a]];
			p[a] = p[b];
		}
	}

	private static int find(int o) {
		return p[o] == o ? o : (p[o] = find(p[o]));
	}

	static class Reader {
		static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

		public Reader(Object... o) {
		}

		public int nextInt() {
			try {
				in.nextToken();
			} catch (Exception ignored) {}
			return (int) in.nval;
		}
	}
}
